{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Range Addition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getModifiedArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #区间加法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假设你有一个长度为&nbsp;<em><strong>n</strong></em>&nbsp;的数组，初始情况下所有的数字均为&nbsp;<strong>0</strong>，你将会被给出&nbsp;<em><strong>k</strong></em>​​​​​​<em>​</em> 个更新的操作。</p>\n",
    "\n",
    "<p>其中，每个操作会被表示为一个三元组：<strong>[startIndex, endIndex, inc]</strong>，你需要将子数组&nbsp;<strong>A[startIndex ... endIndex]</strong>（包括 startIndex 和 endIndex）增加&nbsp;<strong>inc</strong>。</p>\n",
    "\n",
    "<p>请你返回&nbsp;<strong><em>k</em></strong>&nbsp;次操作后的数组。</p>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong>length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]\n",
    "<strong>输出: </strong>[-2,0,3,5,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>解释:</strong></p>\n",
    "\n",
    "<pre>初始状态:\n",
    "[0,0,0,0,0]\n",
    "\n",
    "进行了操作 [1,3,2] 后的状态:\n",
    "[0,2,2,2,0]\n",
    "\n",
    "进行了操作 [2,4,3] 后的状态:\n",
    "[0,2,5,5,3]\n",
    "\n",
    "进行了操作 [0,2,-2] 后的状态:\n",
    "[-2,0,3,5,3]\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [range-addition](https://leetcode.cn/problems/range-addition/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [range-addition](https://leetcode.cn/problems/range-addition/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[1,3,2],[2,4,3],[0,2,-2]]', '10\\n[[2,4,6],[5,6,8],[1,9,-4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        delta: List[int] = [0] * length\n",
    "        for start_index, end_index, inc in updates:\n",
    "            delta[start_index] += inc\n",
    "            if end_index + 1 < length:\n",
    "                delta[end_index + 1] -= inc\n",
    "\n",
    "        A: List[int] = delta\n",
    "        for i in range(1, length):\n",
    "            A[i] = A[i - 1] + A[i]\n",
    "            \n",
    "        return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length, updates):\n",
    "        \"\"\"\n",
    "        :type length: int\n",
    "        :type updates: List[List[int]]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = [0] * length\n",
    "        for i, j, d in updates:\n",
    "            res[i] += d\n",
    "            if j + 1 < length:\n",
    "                res[j + 1] -= d\n",
    "        cur = 0\n",
    "        for i, e in enumerate(res):\n",
    "            cur += e\n",
    "            res[i] = cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        arr = [0] * length\n",
    "        cur = 0\n",
    "        for u, v, a in updates:\n",
    "            arr[u] += a\n",
    "            if v + 1 < length:  arr[v + 1] -= a\n",
    "        for i in range(length):\n",
    "            cur += arr[i]\n",
    "            arr[i] = cur\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        indexChange = defaultdict(int)\n",
    "\n",
    "        for start, end, diff in updates:\n",
    "            indexChange[start] += diff\n",
    "            if end + 1 < length:\n",
    "                indexChange[end + 1] -= diff\n",
    "        \n",
    "        result = []\n",
    "        for i in range(length):\n",
    "            if i in indexChange:\n",
    "                if len(result) == 0:\n",
    "                    newEnd = indexChange[i]\n",
    "                else:\n",
    "                    newEnd = result[-1] + indexChange[i]\n",
    "                result.append(newEnd)\n",
    "            else:\n",
    "                if len(result) > 0:\n",
    "                    result.append(result[-1])\n",
    "                else:\n",
    "                    result.append(0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        #如果在updates中是起点或终点就起点加终点减，然后中间部分一直等于前一个\n",
    "        cnt = defaultdict(int)\n",
    "        res = [0]*length\n",
    "        for x,y,z in updates:\n",
    "            # print(x,y,z)\n",
    "            cnt[x]+=z\n",
    "            cnt[y+1]-=z\n",
    "        exi = sorted(list(cnt))\n",
    "        # print(cnt)\n",
    "        # print(exi)\n",
    "        \n",
    "\n",
    "        for i in range(length):\n",
    "            if i in exi:\n",
    "                res[i] = cnt[i]+res[i-1]\n",
    "            elif i>0 and i not in exi:\n",
    "                res[i] = res[i-1]\n",
    "            # print(res)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        dic={  }\n",
    "        \n",
    "        for j in updates :\n",
    "            st = j[0]\n",
    "            end = j[1]\n",
    "            inc = j[2] \n",
    "            if st in dic:\n",
    "                dic[ st] += inc \n",
    "            else:\n",
    "                dic[ st]=inc \n",
    "            if end == ( length-1 ) :\n",
    "                pass \n",
    "            else:\n",
    "                if ( end +1 ) in dic :\n",
    "                    dic[ end + 1 ] -= inc\n",
    "                    \n",
    "                else:\n",
    "                    dic[ end + 1 ] = -inc  \n",
    "        st=0 \n",
    "        if 0 in dic:\n",
    "            st=dic[0]\n",
    "        else:\n",
    "            st=0\n",
    "        ans=[st ]\n",
    "        for j in range(length )[1:]:\n",
    "            if j in dic:\n",
    "                st= ans[-1] + dic[j]\n",
    "                ans.append( st ) \n",
    "            else:\n",
    "                ans.append( ans[-1])\n",
    "        return ans \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        cache = defaultdict(int)\n",
    "        for start, end, inc in updates:\n",
    "            cache[start] += inc\n",
    "            cache[end + 1] -= inc\n",
    "        res = []\n",
    "        val = 0\n",
    "        for i in range(length):\n",
    "            if i in cache:\n",
    "                val += cache[i]\n",
    "            res.append(val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        # The second problem I met in Online Accessment is like to complete a range addition or intervels additions.\n",
    "        # For example, I am given an integer N. This is the total length of my overall intervel. And I also given some operations, like [1,3,5], which means I should add 5 to each element in intervel from 1 to 3. And finally, I should return an array containing total summation for each index.\n",
    "        # the main idea of my algorithm is to use prefix-sum. I maintained a variable name \"cur-sum\" with initialized value of 0 to track the variation of the summation when I traversed the whole intervel. \n",
    "        # Before I traversed the intervel, I had to divided each update into two operations. The first operation is a tuple of start_index and addition value. And the second operation is a tuple of end_index plus one and the opposite number of addition value. The reason for using opposite number is that I want to keep the consistency of my codes later. I would not have to distinguish whether this operatiion means to start a new addition update or finish an existing update. Since addition updates come into effect immediately, and the expirations of these updates have one index lag, so I plus one for each end_index.(close Intervels for both left boundry and right boundry)  After doing that, I sorted these operations in an increasing order.\n",
    "        # And then I started to traverse the overall interval and go over the operations at the same time. When index_i is equal to some index_stamps of some operations, the cur_sum would add the corresponding value. After that, the index_i takes the cur_sum value as its final summation. \n",
    "\n",
    "        # I can make an improvement. The time complexity would be reduced to O(N+K). Instead of paying attention on prefix-sum and the beginning and end of each update, I would like to focus on the differences between the neighbors. I will mark every variation directly on output array and then rolling the array from the begining to the end to get the final ouput. For example, [2,3,5]. the summation of index_2 will have 5 greater than summation of index_1, so we directly add 5 under the index_2 first. And we know this update will end at index_3, so index_4 will have 5 less than index_3. So we directly substract 5 under the index_4\n",
    "        # After doing that, I will traverse the overall interval and roll the summations from the beginning. S[i] = S[i] + S[i-1]\n",
    "\n",
    "\n",
    "\n",
    "        operations = []\n",
    "        for up in updates: # O(k)\n",
    "            operations.append((up[0], up[2]))\n",
    "            operations.append((up[1]+1, -up[2]))\n",
    "  \n",
    "        operations.sort(key = lambda x: (x[0], x[1])) # O(k logk)\n",
    "\n",
    "        res = []\n",
    "        cur_sum = 0\n",
    "        pointer = 0\n",
    "        # print(operations)\n",
    "        for i in range(length): #O(n + k)\n",
    "            while pointer < len(operations) and i >= operations[pointer][0]:\n",
    "                cur_sum += operations[pointer][1]\n",
    "                pointer += 1\n",
    "            res.append(cur_sum)\n",
    "   \n",
    "        return res\n",
    "\n",
    "    \n",
    "# [1,10], [3, 5, 7 , 15, -1, 10] KlogK\n",
    "# [1->2], [4], [6], [8->10]\n",
    "\n",
    "# [-1, [3, 5, 7, 10], 15] K [8->9]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# The first problem I met in Online Assessment is to return the max length of sub-interval.\n",
    "# I was given a valid range like from 1 to 10, both boundries inclusive. And I was also given an array containing bad numbers.\n",
    "# These bad numbers may within my valid range or not. And these bad numbers split my range into pieces. And every piece could not include these bad numbers. So I was asked to return the longest length of these pieces. \n",
    "\n",
    "# First, I noticed the bad numbers array is unsorted. In order to construct each piece one by one, I had to sort it firstly.\n",
    "# And I used a queue to traverse the bad numbers array. If the bad number the queue pop out is less than my valid range start point, I just continued.\n",
    "# If the popped number is in the range, the length of this piece is equal to this number minus the previous and than minus one. If the popped number is out of our range, I directly return function. And there are also some details about dealing with situations that the boundries of our range are not bad numbers. If these situation happens, we would add one for that piece. \n",
    "# Sorry I cannot remember why I use a queue at that time, maybe it was intuitively to deal with each bad number one by one? Actually, I can just use a pointer to traverse the array, it only cost O(1) space. And the Time complexity is O(N logN) for both algorithm, since we have to sort the bad number array first.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#6/9/2023 yb \n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "\n",
    "        cur = [0 for _ in range(length)]\n",
    "\n",
    "        for start_idx, end_idx, inc in updates:\n",
    "            if start_idx < length:\n",
    "                cur[start_idx] += inc\n",
    "            \n",
    "            if end_idx + 1 < length:\n",
    "                cur[end_idx + 1] -= inc\n",
    "        \n",
    "            #print(cur)\n",
    "\n",
    "        cur_val = cur[0]\n",
    "\n",
    "        for i in range(1,length):\n",
    "            if cur[i] == 0:\n",
    "                cur[i] = cur_val\n",
    "            else:\n",
    "                cur[i] += cur_val\n",
    "                cur_val = cur[i]\n",
    "        \n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        res=[0]*length\n",
    "        for i in range(len(updates)):\n",
    "            res[updates[i][0]] += updates[i][2]\n",
    "            if updates[i][1]<length-1:\n",
    "                res[updates[i][1]+1] -= updates[i][2]\n",
    "        cur=res[0]\n",
    "        for i in range(1,length):\n",
    "            res[i] += cur\n",
    "            cur = res[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        b=[0]*(length+1)\n",
    "        for i,p in enumerate(updates):\n",
    "            b[p[0]]+=p[2]\n",
    "            b[p[1]+1]-=p[2]\n",
    "        res=[0]*(length+1)\n",
    "        for i in range(1,length+1):\n",
    "            res[i]=res[i-1]+b[i-1]\n",
    "        return res[1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        ans=[0]*length\n",
    "        updates=sorted(updates,key=lambda x:x[0])\n",
    "        interval_heap=[]\n",
    "        summ=0\n",
    "        update_idx=0\n",
    "        ans_idx=0\n",
    "        while ans_idx<length:\n",
    "            # 首先，将堆顶endIndex比ans_idx小的元素排除掉\n",
    "            while interval_heap!=[] and interval_heap[0][0]<ans_idx:\n",
    "                update=heapq.heappop(interval_heap)\n",
    "                summ-=update[2]\n",
    "            # 然后，将updates中startIndex不超过ans_idx的元素放入堆中\n",
    "            while update_idx<len(updates) and updates[update_idx][0]<=ans_idx:\n",
    "                update=(updates[update_idx][1],updates[update_idx][0],updates[update_idx][2])\n",
    "                heapq.heappush(interval_heap,update)\n",
    "                summ+=update[2]\n",
    "                update_idx+=1\n",
    "            ans[ans_idx]=summ\n",
    "            ans_idx+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        res = [0] * length\n",
    "        n = len(updates)\n",
    "        for s, n, inc in updates:\n",
    "            res[s] += inc\n",
    "            if (n+1 < length):\n",
    "                res[n+1] -= inc\n",
    "        for i in range(1, length):\n",
    "            res[i] += res[i-1] \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        class DiffArray:\n",
    "            def __init__(self, length):\n",
    "                self.length = length\n",
    "                self.diff = [0 for _ in range(length)]\n",
    "            \n",
    "            def increment(self, start, end, inc):\n",
    "                self.diff[start] += inc\n",
    "                if end < self.length - 1:\n",
    "                    self.diff[end + 1] -= inc\n",
    "            \n",
    "            def result(self):\n",
    "                for i in range(1, self.length):\n",
    "                    self.diff[i] = self.diff[i - 1] + self.diff[i]\n",
    "                return self.diff\n",
    "        \n",
    "        diff = DiffArray(length)\n",
    "        for start, end, inc in updates:\n",
    "            diff.increment(start, end, inc)\n",
    "        return diff.result()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        diff = [0] * (length + 1)\n",
    "        for l, r, d in updates:\n",
    "            diff[l] += d\n",
    "            diff[r + 1] -= d\n",
    "        return list(itertools.accumulate(diff))[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * length\n",
    "        for s, e, inc in updates:\n",
    "            ans[s] += inc\n",
    "            if e + 1 < length:\n",
    "                ans[e + 1] -= inc\n",
    "        curr = 0\n",
    "        for i in range(1, length):\n",
    "            ans[i] += ans[i - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * (length + 1)\n",
    "        for i,j,k in updates:\n",
    "            ans[i] += k\n",
    "            ans[j + 1] -= k\n",
    "        for i in range(1,length):\n",
    "            ans[i] += ans[i-1]\n",
    "        return ans[:-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
